from Nodo import *
from NullNode import *

class RedBlackTree:
    
    red = "red"
    black = "black"
    def __init__(self):
        self.raiz = None
        self.nulo = NullNode()
        
    
    def correr_arvore(self, nodo_raiz):
        if(nodo_raiz != None):
            self.correr_arvore(nodo_raiz.esq())
            nodo_raiz.dado()
            self.correr_arvore(nodo_raiz.dir())
    
    def pesquisar(self, visitador, valor):
        if(visitador == None or valor == visitador.dado()):
            return visitador
        if(valor < visitador.dado()):
            return self.pesquisar(visitador.esq(), valor)
        else:
            return self.pesquisar(visitador.dir(), valor)
    
    def minimo(self, nodo):
        while(nodo.esq() != None):
            nodo = nodo.esq()
        return nodo
    
    def maximo(self, nodo):
        while(nodo.dir() != None):
            nodo = nodo.dir()
        return nodo
    
    def sucessor(self, nodo):
        if(nodo.dir() != None):
            return self.minimo(nodo.dir())
        temp = nodo.pai()
        while(temp != None and nodo == temp.dir()):
            nodo = temp
            temp = temp.pai()
        
        return temp
    
    def predecessor(self, nodo):
        if(nodo.esq() != None):
            return self.maximo(nodo.esq())
        temp = nodo.pai()
        while(temp != None and nodo == temp.esq()):
            nodo = temp
            temp = temp.pai()
        
        return temp
    
    def __RBinsertEsquerdo(self,val,sw):
        if (self.__esquerdo == None):
            self.__esquerdo = RedBlackTree(val)
        else:
            self.__esquerdo.__RBinsert(val,sw)

    def __RBinsertDireito(self,val,sw):
        if (self.__direito == None):
            self.__direito = RedBlackTree(val)
        else:
            self.__direito.__RBinsert(val,sw)
    
    def inserir(self, nodo):        
        nodo.set_cor(self.red)
        nodo.set_esq(self.nulo)
        nodo.set_dir(self.nulo)
        if(self.raiz == None):
            self.raiz = nodo
            self.raiz.set_cor(self.black)
            self.raiz.set_pai(self.nulo)
            return
        y = None
        x = self.raiz
        while x != self.nulo:     
            y = x
            if(nodo.dado() < x.dado()):
                x = x.esq()
            else:
                x = x.dir()
        
        nodo.set_pai(y)
        if(y == None):
            self.raiz = nodo
        elif(nodo.dado() < y.dado()):
            y.set_esq(nodo)
        else:
            y.set_dir(nodo)
        
        nodo.set_esq(self.nulo)
        nodo.set_dir(self.nulo)
        nodo.set_cor(self.red)
        
        #self.insert_fixup(nodo)
        #--------------------------
    
    def insert_fixup(self, nodo):
        
        while(nodo.pai().cor() == self.red):
            if(nodo.pai() == nodo.pai().pai().esq()):
                y = nodo.pai().pai().dir()
                if(y.cor() == self.red):
                    y.set_cor(self.black)
                    nodo.pai().set_cor(self.black)
                    nodo.pai().pai().set_cor(self.red)
                    nodo = nodo.pai().pai()
                else:
                    if(nodo == nodo.pai().dir()):
                        nodo = nodo.pai()
                        print "Rotacionou o " + str(nodo.pai().pai().dado().getNumero()) + " left"
                        self.rotate_left(nodo)
                    nodo.pai().set_cor(self.black)
                    nodo.pai().pai().set_cor(self.red)
                    print "Rotacionou o " + str(nodo.pai().pai().dado().getNumero()) + " right"
                    self.rotate_right(nodo.pai().pai())
            else:
                y = nodo.pai().pai().esq()
                if(y.cor() == self.red):
                    y.set_cor(self.black)
                    nodo.pai().set_cor(self.black)
                    nodo.pai().pai().set_cor(self.red)
                    nodo = nodo.pai().pai()
                else:
                    if(nodo == nodo.pai().esq()):
                        nodo = nodo.pai()
                        print "Rotacionou o " + str(nodo.pai().pai().dado().getNumero()) + " right"
                        self.rotate_right(nodo)
                    nodo.pai().set_cor(self.black)
                    nodo.pai().pai().set_cor(self.red)
                    print "Rotacionou o " + str(nodo.pai().pai().dado().getNumero()) + " left"
                    self.rotate_left(nodo.pai().pai())
                    
        self.raiz.set_cor(self.black)
        
    
    def rotate_left(self, nodo):        
        y = nodo.dir()
        nodo.set_dir(y.esq())
        y.esq().set_pai(nodo)
        y.set_pai(nodo.pai())
        if(nodo.pai() == self.nulo):
            self.raiz = y
        elif(nodo == nodo.pai().esq()):
            nodo.pai().set_esq(y)
        else:
            nodo.pai().set_dir(y)
            
        y.set_esq(nodo)
        nodo.set_pai(y)

    def rotate_right(self, nodo):
        y = nodo.esq()
        nodo.set_esq(y.dir())
        y.dir().set_pai(nodo)
        y.set_pai(nodo.pai())
        if(nodo.pai() == self.nulo):
            self.raiz = y
        elif(nodo == nodo.pai().dir()):
            nodo.pai().set_dir(y)
        else:
            nodo.pai().set_esq(y)
            
        y.set_dir(nodo)
        nodo.set_pai(y)
        
        
    def deletar(self, nodo):
        y = None
        if(nodo.esq() == None or nodo.dir() == None): #caso tenha 1 ou nenhum filho
            y = nodo
        else: # caso tenha 2 filhos
            y = self.sucessor(nodo)
        
        if(y.esq() != None): 
            x = y.esq()
        else: 
            x = y.dir()
          
        if(x != None):
            x.set_pai(y.pai())
            
        if(y.pai() == None): #caso y nao tenha pai ( a raiz)
            self.raiz = x  #a nova raiz ser x
        elif(y == y.pai().esq()): #caso o y seja filho esquerdo
            y.pai().set_esq(x) #o novo filho esquerdo ser x
        elif(y == y.pai().dir()): #caso o y seja filho direito
            y.pai().set_dir(x) #o novo filho direito ser x

        if(y != nodo): #entrar aqui quando o n que ser apagado ter 2 filhos
            nodo.set_dado(y.dado()) #o n que seria apagado ganha o valor do seu sucessor
        
        return y


    def get_raiz(self):
        return self.raiz

    def inorderClass(self,visitor = None,depth=0):
        if(visitor == None):
            visitor = self.raiz
        if visitor.esq() <> self.nulo :
            self.inorderClass(visitor.esq(),depth + 1 )
        print visitor , depth
        if visitor.dir() <> self.nulo :
            self.inorderClass(visitor.dir(),depth + 1 )





